export function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
}

export function createTree(arr, obj = TreeNode) {
  // 创建二叉树
  if (arr.length === 0) return null
  let tree = new obj(arr[0])
  let nodes = [tree]
  let i = 1
  if (i == arr.length) return tree
  for (let node of nodes) {
    if (arr[i] !== null) {
      nodes.push((node.left = new obj(arr[i])))
    }
    i += 1
    if (i == arr.length) return tree
    if (arr[i] !== null) {
      nodes.push((node.right = new obj(arr[i])))
    }
    i += 1
    if (i == arr.length) return tree
  }
}

/**
 * 包含next的二叉树
 */
export function NBinaryNode(val, left, right, next) {
  this.val = val === undefined ? null : val
  this.left = left === undefined ? null : left
  this.right = right === undefined ? null : right
  this.next = next === undefined ? null : next
}

/**
 * [1,#,2,3,#,4,5,6,7,#] => NBinaryNode
 */
export function createNBinaryTree(arr, nextSign = '#') {
  if (arr.length === 0) return null
  let pre = null
  const nodeList = []
  for (let item of arr) {
    const node = item === nextSign ? null : new NBinaryNode(item)
    if (pre) {
      pre.next = node
    }
    if (item === nextSign) {
      pre = null
    } else {
      nodeList.push(node)
      pre = node
    }
  }
  const head = nodeList[0]
  let nodes = [head]
  let i = 1
  if (i == arr.length) return head
  for (let node of nodes) {
    if (node === null) {
      continue
    }
    nodes.push((node.left = nodeList[i] || null))
    i += 1
    if (i == arr.length) break
    nodes.push((node.right = nodeList[i] || null))
    i += 1
    if (i == arr.length) break
  }
  return head
}

/**
多叉树
 */
export function MultiNode(val, children) {
  this.val = val
  this.children = children || null
}

export function createMultiTree(arr) {
  if (arr.length === 0) return null
  let res = null
  let levelNodes = []
  let newLevelNodes = []
  let pre = null
  for (let i = 0; i < arr.length; i++) {
    const item = arr[i]
    if (item === null) {
      if (levelNodes.length === 0) {
        levelNodes = [...newLevelNodes]
        newLevelNodes = []
        // pre = null
      }
      pre = levelNodes.shift()
      continue
    }
    const nodeItem = new MultiNode(item)
    newLevelNodes.push(nodeItem)
    if (i === 0) {
      res = nodeItem
    }
    if (pre) {
      pre.children = pre.children || []
      pre.children.push(nodeItem)
    }
  }
  return res
}
